#! /usr/bin/env python
# coding=utf8

class TBaseGraph:
    def GetVertexCount(self):
        return 0

    def GetAdj(self, vertexNum):
        return []

    def GetWeight(self, fromV, toV):
        return 0

class TGraphMatrix(TBaseGraph):
    def __init__(self, matrix):
        self.Matrix = matrix

    def GetVertexCount(self):
        return len(self.Matrix)

    # Get weights of out edjes of given vertex
    def GetAdj(self, vertexNum):
        ret = []
        for i in range(len(self.Matrix[vertexNum])):
            if self.Matrix[vertexNum][i] is not None:
                ret.insert(len(ret), i)
        return ret

    def GetWeight(self, fromV, toV):
        return self.Matrix[fromV][toV]

class TPriorityQueue:
    def __init__(self, items, priorities, priorityFunc = lambda x, y: (x is not None and y is None) or (x is not None and y is not None and x < y)):
        self.Elements = [(items[i], priorities[i]) for i in range(len(items))] # копируем элементы к себе
        self.PriorityFunc = priorityFunc

    def Pop(self):
        if not len(self.Elements):
            return
        best = 0
        for i in range(len(self.Elements)):
            item, priority = self.Elements[i]
            bestItem, bestPriority = self.Elements[best]
            if self.PriorityFunc(priority, bestPriority):
                best = i
        bestItem, bestPriority = self.Elements[best]
        del self.Elements[best]
        return bestItem

    def UpdatePriority(self, item, priority):
        for i in range(len(self.Elements)):
            it, pr = self.Elements[i]
            if it == item:
                self.Elements[i] = (item, priority)
                return

    def IsEmpty(self):
        return len(self.Elements) == 0


def Relax(graph, fromV, toV, d, p, queue):
    newDistance = d[fromV] + graph.GetWeight(fromV, toV)
    if d[toV] is None or newDistance < d[toV]:
        d[toV] = newDistance
        p[toV] = fromV
        queue.UpdatePriority(toV, newDistance)

def Dijkstra(graph, sourceVertex):
    vertexCount = graph.GetVertexCount()
    d = [None for i in range(vertexCount)]
    p = [None for i in range(vertexCount)] # предшественники
    d[sourceVertex] = 0
    queue = TPriorityQueue([i for i in range(vertexCount)], d)

    while not queue.IsEmpty():
        v = queue.Pop()
        for u in graph.GetAdj(v):
            Relax(graph, v, u, d, p, queue)
    return (d, p)

def PrintShortestPath(fromV, toV, shortestLen, shortestPaths):
    print "{} -> {}: {}: ".format(fromV, toV, shortestLen[toV])
    path = []
    i = toV
    while i is not None:
        path.append(i)
        i = shortestPaths[i]

    print "\t",
    for v in range(len(path) - 1, -1, -1):
        print "({})".format(path[v]),
        if path[v] != toV:
            print " - ",
    print ""

def run_sample(matrix):
    graph = TGraphMatrix(matrix)
    for fromV in range(graph.GetVertexCount()):
        shortestLen, shortestPaths = Dijkstra(graph, fromV)
        print "Paths from vertex {} with weights:".format(fromV)
        for i in range(graph.GetVertexCount()):
            PrintShortestPath(fromV, i, shortestLen, shortestPaths)
        print ""

def run_samples():
    matrix = [
        [None, 7, 9, None, None, 14],
        [7, None, 10, 15, None, None],
        [9, 10, None, 11, None, 2],
        [None, 15, 11, None, 6, None],
        [None, None, None, 6, None, 9],
        [14, None, 2, None, 9, None]
    ]
    run_sample(matrix)

    matrix = [
        [None, 7, 9, None, None, 14],
        [None, None, 10, 15, 10, 5],
        [99, 10, None, 13, None, 2],
        [3, 1, 11, None, 8, 7],
        [None, 6, None, 3, None, 8],
        [None, None, 1, 18, 6, None]
    ]
    run_sample(matrix)

def main():
    run_samples()

if __name__ == "__main__":
    main()
